package tree;
//https://leetcode.cn/leetbook/read/illustration-of-algorithm/7fjekj/
public class 将二叉搜索树转化为排序的双向链表 {
    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }
    class Solution {
        //把每个结点的left看作双向链表里的pre，right看作双向链表里的next，更容易理解
        Node pre, head;
        public Node treeToDoublyList(Node root) {
            if(root == null || root.val == 0) return null;
            dfs(root);
            //中序遍历处理过后只是形成了一个双向链表
            //让头结点的pre指向尾结点，尾结点的next指向头，才形成循环
            head.left = pre; //头尾循环
            pre.right = head;
            return head;
        }
        void dfs(Node cur) {//中序遍历基本结构：left,自身,right
            if(cur == null) return;
            dfs(cur.left);
            //如果头结点为空，说明这是双向链表里的第一个结点
            //对头结点只需要处理它的next指针，也就是root.left = pre;
            if(pre != null) pre.right = cur;
            else head = cur;
            cur.left = pre;
            pre = cur;
            dfs(cur.right);//cur会随着遍历延伸，不需要更新
        }
    }
}
